package GraphType.digitalPyramid;

import java.util.Scanner;

import static GraphType.shortestPath.DFS.printMatrix;

public class DP {
    static int[][] a = new int[10][10];
    static int[][] f = new int[10][10];//f[x][y]表示从起点1,1到达x,y所经过的路径最大权值和
    static int ans;
    static int n;

    public static void main(String[] args) {
        init();
        dp2();
    }

    private static void dp() {
        f[1][1]=1;
        for (int i = 2; i <=n ; i++) {
            for (int j = 1; j <=i ; j++) {
                f[i][j]=Math.max(f[i-1][j],f[i-1][j-1])+a[i][j];
            }
        }
        for (int i = 1; i <=n ; i++) {
            ans = Math.max(ans,f[n][i]);
        }
        System.out.println(ans);
    }

    private static void dp2() {
        //边界初始化
        if (n >= 0) System.arraycopy(a[n], 1, f[n], 1, n);
        //动态规划逆推法
        for (int i = n-1; i >=1 ; i--) {
            for (int j = 1; j <=i ; j++) {
                f[i][j] = Math.max(f[i+1][j],f[i+1][j+1])+a[i][j];
            }
        }
        System.out.println(f[1][1]);
    }

    static void init() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = scanner.nextInt();
            }
        }
        printMatrix(a);
        ans = 0;
    }
}
